package algorithm.sort;

import java.util.Arrays;

public class QuickSort {


    public static void main(String[] args) {
        // 希尔排序，基于插入排序，缩小增量排序，n/2,n/2/2 直到1的增量比较大小，让左边都是较小的元素
        // 从小到大排序
        System.out.println("======推导========");
        deductionQuick();
        System.out.println("======准备数据========");
        int[] arr = TestHelp.random(10);
        int[] arrCopy = Arrays.copyOfRange(arr,0,10);
        TestHelp.print("比较前",arr);
        long begin = TestHelp.begin();
        quick(arr,0,arr.length-1,1);
        TestHelp.end(begin);
        TestHelp.print("比较后",arr);
        System.out.println("======中心点更换位置========");
        TestHelp.print("比较前",arrCopy);
        begin = TestHelp.begin();
        quick(arrCopy,0,arrCopy.length-1,1);
        TestHelp.end(begin);
        TestHelp.print("比较后",arrCopy);
    }

    /**
     * 快速排序 中心值 左边，右边
     * 时间复杂度O(n^2)-O(nlogn)
     * 空间复杂度O(1)，只需要一个临时变量
     * 不稳定，相同元素的位置会变换，
     */
    public static void quick(int[] arr,int start,int end,int counter){
        if(start >= end){
            return;
        }
        int pivot = start;//哨兵位置，从右往左移时，开始交换
        int pivotValue = arr[pivot];// 中心点的数值，
        int low = start;
        int high = end;

        while(low < high){
            // 中心值是第一个元素，所以先从高指针向左移，不符合条件，将左边从0开始替换成高位元素
            // 高指针
            while(low < high && arr[high] >= pivotValue){
                high--;// 向左移
            }

            arr[low]=arr[high];
            // 低指针所在值小于中心值，向右移
            while(low < high && arr[low] <= pivotValue){
                low++;// 向右移
            }
            // 如果低指针移动到不符合条件，会跳出循环
            arr[high] = arr[low];

        }
        TestHelp.print("中心值替换前",arr);
        // 最低位置的元素与中心值交换
        arr[low]=pivotValue;
        TestHelp.print("low",low);//
        TestHelp.print("high",high);// 低指针与高指针重合
        TestHelp.print("第"+counter+"趟",arr);
        // 左边
        quick(arr,start,low,counter+1);
        // 右边
        quick(arr,low+1,end,counter+1);

    }

    /**
     * 快速排序 中心值 左边，右边
     * 时间复杂度O(n^2)-O(nlogn)
     * 空间复杂度O(1)，只需要一个临时变量
     * 不稳定，相同元素的位置会变换，
     */
    public static void quickPivod(int[] arr,int start,int end,int counter){
        if(start >= end){
            return;
        }
        int pivot = (end+start)/2;//中心点，取近似中间位置的数
        int pivotValue = arr[pivot];// 中心点的数值，
        int low = start;
        int high = end;

        while(low < high){
            // 中心值是第一个元素，所以先从高指针向左移，不符合条件，将左边从0开始替换成高位元素
            // 高指针
            while(low < high && arr[high] >= pivotValue){
                high--;// 向左移
            }

            arr[low]=arr[high];
            // 低指针所在值小于中心值，向右移
            while(low < high && arr[low] <= pivotValue){
                low++;// 向右移
            }
            // 如果低指针移动到不符合条件，会跳出循环
            arr[high] = arr[low];

        }
        TestHelp.print("中心值替换前",arr);
        // 最低位置的元素与中心值交换
        arr[low]=pivotValue;
        TestHelp.print("low",low);//
        TestHelp.print("high",high);// 低指针与高指针重合
        TestHelp.print("第"+counter+"趟",arr);
        // 左边
        quick(arr,start,low,counter+1);
        // 右边
        quick(arr,low+1,end,counter+1);

    }

    /**
     * 逐步推导，演绎，先从第二个元素，第三个元素。。一个个元素排序处理
     */
    public static void deductionQuick(){
        int[] arr = new int[]{8,3,12,6,19,2,33,1,2,5};
        // 选择中心点，以第1个元素为中心点，两个指针，低位指针向右移，高位指针向左移，当重合时结束
        // 第一趟============
        int pivot = 0;//哨兵位置，从右往左移时，开始交换
        int pivotValue = arr[pivot];// 中心点的数值，
        int low = 0;
        int high = arr.length-1;

        while(low < high){
            // 中心值是第一个元素，所以先从高指针向左移，不符合条件，将左边从0开始替换成高位元素
            // 高指针
            while(low < high && arr[high] >= pivotValue){
                high--;// 向左移
            }

            arr[low]=arr[high];
            // 低指针所在值小于中心值，向右移
            while(low < high && arr[low] <= pivotValue){
                low++;// 向右移
            }
            // 如果低指针移动到不符合条件，会跳出循环
            arr[high] = arr[low];

        }
        /**
         * 5,3,12,6,19,2,33,1,2,8 low=0,high=9
         * 5,3,12,6,19,2,33,1,2,8 low=1,high=9
         * 5,3,8,6,19,2,33,1,2,12 low=2,high=9
         * 5,3,2,6,19,2,33,1,8,12 low=2,high=8
         * 5,3,2,6,19,2,33,1,8,12 low=3,high=8
         * 5,3,2,6,8,2,33,1,19,12 low=4,high=8
         * 5,3,2,6,1,2,33,8,19,12 low=4,high=7
         * 5,3,2,6,1,2,33,8,19,12 low=5,high=7
         * 5,3,2,6,1,2,33,33,19,12 low=6,high=7
         * 5,3,2,6,1,2,33,33,19,12 low=6,high=6
         */
        TestHelp.print("中心值替换前",arr);// [5, 3, 2, 6, 1, 2, 33, 33, 19, 12]
        // 最低位置的元素与中心值交换
        arr[low]=pivotValue;
        TestHelp.print("low",low);//6
        TestHelp.print("high",high);//6 低指针与高错针重合
        TestHelp.print("第一趟",arr);// [5, 3, 2, 6, 1, 2, 8, 33, 19, 12]
        // 第二趟--左边[5, 3, 2, 6, 1, 2, 8][33, 19, 12]
        pivot = 0;//哨兵位置，从右往左移时，开始交换
        pivotValue = arr[pivot];// 中心点的数值
        low = 0;
        while(low < high){
            // 中心值是第一个元素，所以先从高指针向左移，不符合条件，将左边从0开始替换成高位元素
            // 高指针
            while(low < high && arr[high] >= pivotValue){
                high--;// 向左移
            }

            arr[low]=arr[high];
            // 低指针所在值小于中心值，向右移
            while(low < high && arr[low] <= pivotValue){
                low++;// 向右移
            }
            // 如果低指针移动到不符合条件，会跳出循环
            arr[high] = arr[low];

        }

        TestHelp.print("中心值替换前",arr);// [2, 3, 2, 1, 1, 6, 8]
        // 最低位置的元素与中心值交换
        arr[low]=pivotValue;
        TestHelp.print("low",low);//
        TestHelp.print("high",high);//
        TestHelp.print("第二趟左边",arr);// [2, 3, 2, 1, 5, 6, 8]

        // 第二趟--右边[5, 3, 2, 6, 1, 2, 8][33, 19, 12]
        pivot = 7;//哨兵位置，从右往左移时，开始交换
        pivotValue = arr[pivot];// 中心点的数值
        low = 7;
        high = arr.length-1;
        while(low < high){
            // 中心值是第一个元素，所以先从高指针向左移，不符合条件，将左边从0开始替换成高位元素
            // 高指针
            while(low < high && arr[high] >= pivotValue){
                high--;// 向左移
            }

            arr[low]=arr[high];
            // 低指针所在值小于中心值，向右移
            while(low < high && arr[low] <= pivotValue){
                low++;// 向右移
            }
            // 如果低指针移动到不符合条件，会跳出循环
            arr[high] = arr[low];

        }

        TestHelp.print("中心值替换前",arr);// [2, 3, 2, 1, 1, 6, 8]
        // 最低位置的元素与中心值交换
        arr[low]=pivotValue;
        TestHelp.print("low",low);//
        TestHelp.print("high",high);//
        TestHelp.print("第二趟右边",arr);// [2, 3, 2, 1, 5, 6, 8]
    }
}
